#ifndef TEST_PY_TABU_REFINER_H
#define TEST_PY_TABU_REFINER_H

#include "refiner_base.h"
#include "sp_set.h"
#include "timer.h"

namespace mcgpp {
  class TabuRefiner : public RefinerBase {
  public:
    TabuRefiner(ds::GenericGraph &graph) : RefinerBase(graph),
                                           ttenure(graph.initialNumNodes()) {
      max_iter = Context::instance().localSearchParameters.ta.max_iter;
      alfa = Context::instance().localSearchParameters.ta.alfa;
      p_interval = max_iter / period_size;
    }

    virtual void initializeImpl() override {
      metrics::conductance(_g, current_obj);
      best_obj = current_obj;
      saveBestSol();

      cut_nodes.clear();
      for (auto u: _g._current_node_set) {
        ttenure[u] = 0;
        if (isBorderNode(u))
          cut_nodes.add(u);
      }

    }



    //不约束邻域版本
    void refineImpl() override {
      int iter = 0;
      int t = 0, p = 0;//决定禁忌时机
      Metrics new_obj;
//    // ll tabu_best, no_tabu_best;
      Metrics tabu_best_obj, no_tabu_best_obj;
      int tabu_cnt, no_tabu_cnt;
      IDType tabu_v, no_tabu_v, best_v;

      while (iter < max_iter) {
        tabu_best_obj.reset();
        no_tabu_best_obj.reset();
        tabu_v = -1;
        no_tabu_v = -1;
        best_v = -1;
        tabu_cnt = 0;
        no_tabu_cnt = 0;
        //评估
        for (auto v: cut_nodes) {

          ll delta = moveNodeGain(v, _g.partID(v), 1 ^ _g.partID(v), current_obj, new_obj);
          if (delta == invalidGain)//确保移动都是有效的
            continue;
          if (ttenure[v] < iter) {
            //处于禁忌状态的
            if (new_obj < tabu_best_obj) {
              //选择最优的或者等概率最小的接受
              tabu_v = v;
              tabu_best_obj = new_obj;
              tabu_cnt = 0;
            } else if (new_obj == tabu_best_obj && Randomize::instance().getRandomInt(0, ++tabu_cnt) == 0)
              tabu_v = v;

          } else {
            //处于非禁忌状态
            if (new_obj < no_tabu_best_obj) {
              //选择最优的或者等概率最小的接受
              no_tabu_v = v;
              no_tabu_best_obj = new_obj;
              no_tabu_cnt = 0;
            } else if (new_obj == no_tabu_best_obj && Randomize::instance().getRandomInt(0, ++no_tabu_cnt) == 0)
              no_tabu_v = v;
          }

        }
        //1.首先考虑禁忌解的接受
        //eg1.禁忌解比非禁忌解好而且比当前解好
        //eg2.没有找到非禁忌动作
        if (tabu_v != -1 && tabu_best_obj <= no_tabu_best_obj && tabu_best_obj <= current_obj
            || no_tabu_v == -1) {
          //执行禁忌解
          current_obj = tabu_best_obj;
          best_v = tabu_v;
        } else {
          current_obj = no_tabu_best_obj;
          best_v = no_tabu_v;
        }
//        LOG << "make move:" << best_v << _g.partID(best_v) << 1 - _g.partID(best_v);
        //2.执行移动并更新禁忌表
        changeNodePart(best_v, _g.partID(best_v), 1 ^ _g.partID(best_v));
        ttenure[best_v] = iter + 1 + period[p] * alfa;
        ++t;
        if (t > p_interval) {
          p = (p + 1) % period_size;
          t = 0;
        }
        //3.保存最优解
        if (current_obj < best_obj) {
          saveBestSol();
          iter = 0;
        } else
          ++iter;

        if (Timer::instance().TLE())
          break;
      }

      //恢复最优解
      current_obj = best_obj;
      for (auto v: _g._current_node_set) {
        if (_g.partID(v) != best_partition[v])
          changeNodePart(v, _g.partID(v), 1 - _g.partID(v));

      }

//      LOG << "after ta obj =" << static_cast<double>(current_obj.conductance / 1e10);
//      checkDataStructure();
    }


    void checkDataStructure() {
//      //检查每个点的weight计算
      _g.check();
      //检查切点
      int cut_node_count = 0;
      for (auto v: _g._current_node_set) {
        if (isBorderNode(v)) {
          ++cut_node_count;
          if (!cut_nodes.contains(v))
            ERROREXIT("cut node error!");
        }
      }
      if (cut_node_count != cut_nodes.size())
        ERROREXIT("cut node count error!");
//      //检查解是否有问题
      ll cut_num = 0, cut_weight = 0;
      Vec<ll> partInfo_num(2), partInfo_weight(2), partInfo_t_weight(2);
      for (auto v: _g._current_node_set) {
        int pid = _g.partID(v);
        partInfo_num[pid] += _g.node(v).total_edge_num;
        partInfo_weight[pid] += _g.node(v).total_edge_weight;
        partInfo_t_weight[pid] += _g.node(v).weight();
      }
      for (int i = 0; i < _g._num_edges; ++i) {
        if (_g.edgeIsEnabled(i) && _g._connectivity_sets[i].bit() == 3) {
          cut_weight += _g.edge(i).weight();
          cut_num += 1;
        }
      }
      ll volume = 0;
      switch (Context::instance().objMetric) {
        case ObjMetric::cut_num:
          if (cut_num != current_obj.cut_num) {
            LOG << "cut num:" << cut_num << current_obj.cut_num;
            metrics::conductance(_g);
            ERROREXIT("cut num error!");
          }
          if (partInfo_num[0] != _g._part_info[0].num || partInfo_num[1] != _g._part_info[1].num) {
            LOG << partInfo_num[0] << partInfo_num[1];
            LOG << _g._part_info[0].num << _g._part_info[1].num;
            ERROREXIT("part info num error!");
          }
          {
            volume = std::min(partInfo_num[0], partInfo_num[1]);
            if (volume != current_obj.volume_num) {
              LOG << volume << current_obj.volume_num;
              ERROREXIT("volume num error!");
            }
            ll cond = (static_cast<double>(cut_num) / static_cast<double>(volume)) * 1e10;
            if (cond != current_obj.conductance)
              ERROREXIT("cond error!");
          }
          break;
        case ObjMetric::cut_weight:
          if (cut_weight != current_obj.cut_weight) {
            LOG << "cut weight:" << cut_weight << current_obj.cut_weight;
            metrics::conductance(_g);
            ERROREXIT("cut weight error!");
          }
          if (partInfo_weight[0] != _g._part_info[0].weight || partInfo_weight[1] != _g._part_info[1].weight) {
            LOG << partInfo_weight[0] << partInfo_weight[1];
            LOG << _g._part_info[0].weight << _g._part_info[1].weight;
            ERROREXIT("part info weight error!");
          }
          {
            volume = std::min(partInfo_weight[0], partInfo_weight[1]);
            if (volume != current_obj.volume_weight) {
              LOG << volume << current_obj.volume_weight;
              ERROREXIT("volume weight error!");
            }
            ll cond = (static_cast<double>(cut_weight) / static_cast<double>(volume)) * 1e10;
            if (cond != current_obj.conductance)
              ERROREXIT("cond error!");
          }
          break;
        case ObjMetric::real:
          if (cut_weight != current_obj.cut_weight) {
            LOG << "cut weight:" << cut_weight << current_obj.cut_weight;
            metrics::conductance(_g);
            ERROREXIT("cut weight error!");
          }
          if (partInfo_t_weight[0] != _g._part_info[0].t_weight || partInfo_t_weight[1] != _g._part_info[1].t_weight) {
            LOG << partInfo_t_weight[0] << partInfo_t_weight[1];
            LOG << _g._part_info[0].t_weight << _g._part_info[1].t_weight;
            ERROREXIT("part info t weight error!");
          }
          {
            volume = std::min(partInfo_t_weight[0], partInfo_t_weight[1]);
            if (volume != current_obj.volume_t_weight) {
              LOG << volume << current_obj.volume_t_weight;
              ERROREXIT("volume weight error!");
            }
            ll cond = (static_cast<double>(cut_weight) / static_cast<double>(volume)) * 1e10;
            if (cond != current_obj.conductance)
              ERROREXIT("cond error!");
          }
          break;
        default:
          ERROREXIT("obj metric error!");
      }
    }

    //禁忌周期
    int p_interval;//动态决定：max_iter/period_size
    int period_size = 15;
    const int period[15] = {10, 20, 10, 40, 10, 20, 10, 80, 10, 20, 10, 40, 10, 20, 10};

    //禁忌表
    std::vector<int> ttenure;
    int max_iter;//连续未改进的最大迭代数
    int alfa;//禁忌周期管理因子
  };
}
#endif //TEST_PY_TABU_REFINER_H
